/*
 * This regular expression implementation is adapted from Russ Cox's
 * implementation.  See http://swtch.com/~rsc/regexp/ for more information
 * on the original algorithm and implementation.
 *
 * Supports only ( | ) * + ?.  No escapes. Compiles to NFA and then simulates
 * NFA using Thompson's algorithm.  Caches steps of Thompson's algorithm to
 * build DFA on the fly, as in Aho's egrep.
 *
 * See also Thompson, Ken.  Regular Expression Search Algorithm,
 * Communications of the ACM 11(6) (June 1968), pp. 419-422.
 *
 * The original code by Russ Cox was released under the MIT License and as such
 * the license is included below:
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/*
 * Convert infix regexp re to postfix notation.
 * Insert . as explicit concatenation operator.
 * Cheesy parser, return static buffer.
 */
char* re2postfix(char* re)
{
	int nalt, natom;
	static char buf[8000];
	char* dst;

	struct
	{
		int nalt;
		int natom;
	} paren[100], *p;

	p = paren;
	dst = buf;
	nalt = 0;
	natom = 0;
	if(strlen(re) >= sizeof buf/2)
		return NULL;

	for(; *re; re++) switch(*re)
	{
		case '(':
			if(natom > 1)
			{
				--natom;
				*dst++ = '.';
			}

			if(p >= paren+100)
				return NULL;

			p->nalt = nalt;
			p->natom = natom;
			p++;
			nalt = 0;
			natom = 0;
			break;

		case '|':
			if(natom == 0)
				return NULL;
			while(--natom > 0)
				*dst++ = '.';
			nalt++;
			break;

		case ')':
			if(p == paren)
				return NULL;
			if(natom == 0)
				return NULL;
			while(--natom > 0)
				*dst++ = '.';
			for(; nalt > 0; nalt--)
				*dst++ = '|';
			--p;
			nalt = p->nalt;
			natom = p->natom;
			natom++;
			break;

		case '*':
		case '+':
		case '?':
			if(natom == 0)
				return NULL;
			*dst++ = *re;
			break;

		default:
			if(natom > 1)
			{
				--natom;
				*dst++ = '.';
			}

			*dst++ = *re;
			natom++;
			break;
	}

	if(p != paren)
		return NULL;

	while(--natom > 0)
		*dst++ = '.';

	for(; nalt > 0; nalt--)
		*dst++ = '|';

	*dst = 0;

	return buf;
}

/*
 * Represents an NFA state plus zero or one or two arrows exiting.
 * if c == Match, no arrows out; matching state.
 * If c == Split, unlabeled arrows to out and out1 (if != NULL).
 * If c < 256, labeled arrow with character c to out.
 */
enum
{
	MATCH = 256,
	SPLIT = 257
};

struct State
{
	int c;
	struct State* out;
	struct State* out1;
	int lastlist;
};

struct State matchstate = { MATCH };	/* matching state */
int nstate;

/* Allocate and initialize State */
struct State* state(int c, struct State* out, struct State* out1)
{
	struct State* s;

	nstate++;
	s = malloc(sizeof(struct State));
	s->lastlist = 0;
	s->c = c;
	s->out = out;
	s->out1 = out1;
	return s;
}

/*
 * A partially built NFA without the matching state filled in.
 * Frag.start points at the start state.
 * Frag.out is a list of places that need to be set to the
 * next state for this fragment.
 */
struct Frag
{
	struct State *start;
	union Ptrlist *out;
};

/* Initialize Frag struct. */
struct Frag frag(struct State *start, union Ptrlist *out)
{
	struct Frag n = { start, out };
	return n;
}

/*
 * Since the out pointers in the list are always
 * uninitialized, we use the pointers themselves
 * as storage for the Ptrlists.
 */
union Ptrlist
{
	union Ptrlist *next;
	struct State *s;
};

/* Create singleton list containing just outp. */
union Ptrlist* list1(struct State **outp)
{
	union Ptrlist *l;

	l = (union Ptrlist*)outp;
	l->next = NULL;
	return l;
}

/* Patch the list of states at out to point to start. */
void patch(union Ptrlist *l, struct State *s)
{
	union Ptrlist *next;

	for(; l; l=next)
	{
		next = l->next;
		l->s = s;
	}
}

/* Join the two lists l1 and l2, returning the combination. */
union Ptrlist* append(union Ptrlist *l1, union Ptrlist *l2)
{
	union Ptrlist *oldl1;

	oldl1 = l1;

	while(l1->next)
		l1 = l1->next;

	l1->next = l2;

	return oldl1;
}

/*
 * Convert postfix regular expression to NFA.
 * Return start state.
 */
struct State* post2nfa(char *postfix)
{
	char *p;
	struct Frag stack[1000], *stackp, e1, e2, e;
	struct State *s;

	// fprintf(stderr, "postfix: %s\n", postfix);

	if(postfix == NULL)
		return NULL;

	#define push(s) *stackp++ = s
	#define pop() *--stackp

	stackp = stack;
	for(p=postfix; *p; p++) switch(*p)
	{
		default:
			s = state(*p, NULL, NULL);
			push(frag(s, list1(&s->out)));
			break;
		case '.':	/* catenate */
			e2 = pop();
			e1 = pop();
			patch(e1.out, e2.start);
			push(frag(e1.start, e2.out));
			break;
		case '|':	/* alternate */
			e2 = pop();
			e1 = pop();
			s = state(SPLIT, e1.start, e2.start);
			push(frag(s, append(e1.out, e2.out)));
			break;
		case '?':	/* zero or one */
			e = pop();
			s = state(SPLIT, e.start, NULL);
			push(frag(s, append(e.out, list1(&s->out1))));
			break;
		case '*':	/* zero or more */
			e = pop();
			s = state(SPLIT, e.start, NULL);
			patch(e.out, s);
			push(frag(s, list1(&s->out1)));
			break;
		case '+':	/* one or more */
			e = pop();
			s = state(SPLIT, e.start, NULL);
			patch(e.out, s);
			push(frag(e.start, list1(&s->out1)));
			break;
	}

	e = pop();
	if(stackp != stack)
		return NULL;

	patch(e.out, &matchstate);
	return e.start;
#undef pop
#undef push
}

struct StateList
{
	struct State **s;
	int n;
};

struct StateList l1, l2;
static int listid;

void addstate(struct StateList*, struct State*);
void step(struct StateList*, int, struct StateList*);

/* Compute initial state list */
struct StateList* startlist(struct State *start, struct StateList *l)
{
	l->n = 0;
	listid++;
	addstate(l, start);
	return l;
}

/* Check whether state list contains a match. */
int ismatch(struct StateList *l)
{
	int i;

	for(i=0; i<l->n; i++)
		if(l->s[i] == &matchstate)
			return 1;

	return 0;
}

/* Add s to l, following unlabeled arrows. */
void addstate(struct StateList *l, struct State *s)
{
	if(s == NULL || s->lastlist == listid)
		return;
	s->lastlist = listid;

	if(s->c == SPLIT)
	{
		/* follow unlabeled arrows */
		addstate(l, s->out);
		addstate(l, s->out1);
		return;
	}

	l->s[l->n++] = s;
}

/*
 * Step the NFA from the states in clist
 * past the character c,
 * to create next NFA state set nlist.
 */
void step(struct StateList *clist, int c, struct StateList *nlist)
{
	int i;
	struct State *s;

	listid++;
	nlist->n = 0;
	for(i=0; i<clist->n; i++){
		s = clist->s[i];
		if(s->c == c)
			addstate(nlist, s->out);
	}
}

/*
 * Represents a DFA state: a cached NFA state list.
 */
struct DState
{
	struct StateList l;
	struct DState *next[256];
	struct DState *left;
	struct DState *right;
};

/* Compare lists: first by length, then by members. */
static int listcmp(struct StateList *l1, struct StateList *l2)
{
	int i;

	if(l1->n < l2->n)
		return -1;

	if(l1->n > l2->n)
		return 1;

	for(i=0; i<l1->n; i++)
	{
		if(l1->s[i] < l2->s[i])
			return -1;

		else if(l1->s[i] > l2->s[i])
			return 1;
	}

	return 0;
}

/* Compare pointers by address. */
static int ptrcmp(const void *a, const void *b)
{
	if(a < b)
		return -1;
	if(a > b)
		return 1;
	return 0;
}

struct DState *freelist;

/* Allocate DStates from a cached list. */
struct DState* allocdstate()
{
	struct DState *d;

	if((d = freelist) != NULL)
		freelist = d->left;

	else
	{
		d = malloc(sizeof *d + nstate*sizeof(struct State*));
		d->l.s = (struct State**)(d+1);
	}

	d->left = NULL;
	d->right = NULL;
	memset(d->next, 0, sizeof d->next);
	return d;
}

/* Free the tree of states rooted at d. */
void freestates(struct DState *d)
{
	if(d == NULL)
		return;
	freestates(d->left);
	freestates(d->right);
	d->left = freelist;
	freelist = d;
}

static struct DState *alldstates;
static int nstates;

/* Throw away the cache and start over. */
void freecache(void)
{
	freestates(alldstates);
	alldstates = NULL;
	nstates = 0;
}

/*
 * Return the cached DState for list l,
 * creating a new one if needed.
 */
int maxstates = 32;
struct DState* dstate(struct StateList *l, struct DState **nextp)
{
	int i;
	struct DState **dp, *d;

	qsort(l->s, l->n, sizeof l->s[0], ptrcmp);
	dp = &alldstates;

	while((d = *dp) != NULL)
	{
		i = listcmp(l, &d->l);
		if(i < 0)
			dp = &d->left;
		else if(i > 0)
			dp = &d->right;
		else
			return d;
	}

	if(nstates >= maxstates)
	{
		freecache();
		dp = &alldstates;
		nextp = NULL;
	}

	d = allocdstate();
	memmove(d->l.s, l->s, l->n*sizeof l->s[0]);
	d->l.n = l->n;
	*dp = d;
	nstates++;
	if(nextp != NULL)
		*nextp = d;
	return d;
}

void startnfa(struct State *start, struct StateList *l)
{
	l->n = 0;
	listid++;
	addstate(l, start);
}

struct DState* startdstate(struct State *start)
{
	return dstate(startlist(start, &l1), NULL);
}

struct DState* nextstate(struct DState *d, int c)
{
	step(&d->l, c, &l1);
	return dstate(&l1, &d->next[c]);
}

/* Run DFA to determine whether it matches s. */
int match(struct DState *start, char *s)
{
	struct DState *d, *next;
	int c;

	d = start;
	for(; *s; s++){
		c = *s & 0xFF;
		if((next = d->next[c]) == NULL)
			next = nextstate(d, c);
		d = next;
	}

	return ismatch(&d->l);
}

int main(int argc, char **argv)
{
	int i;
	char* post;
	struct State* start;

	if(argc < 3)
	{
		fprintf(stderr, "usage: nfa regexp string...\n");
		return 1;
	}

	post = re2postfix(argv[1]);

	if(post == NULL)
	{
		fprintf(stderr, "bad regexp %s\n", argv[1]);
		return 1;
	}

	start = post2nfa(post);

	if(start == NULL)
	{
		fprintf(stderr, "error in post2nfa %s\n", post);
		return 1;
	}

	l1.s = malloc(nstate*sizeof l1.s[0]);
	l2.s = malloc(nstate*sizeof l2.s[0]);

	for(i=2; i<argc; i++)
		if(match(startdstate(start), argv[i]))
			printf("%s\n", argv[i]);

	return 0;
}

